package main

/*
算法
矩阵的行列试
*/
func Determinant(matrix [][]int) int {
	// your code here
	rows := len(matrix)
	cols := len(matrix[0])

	return determinantSub2(matrix, rows, cols)
}

// det(M) = a * det(a_minor) - b * det(b_minor) + c * det(c_minor) - d * det(d_minor)
func determinantSub2(matrix [][]int, rows, col int) int {
	if rows == 1 {
		return matrix[0][0]
	}
	if rows == 2 {
		return (matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1])
	}

	tempDet := make([][]int, 0)
	for i := 0; i <= rows-1; i++ {
		temp := make([]int, rows-1)
		tempDet = append(tempDet, temp)
	}

	var res int
	for i := 0; i < rows; i++ {
		for j := 0; j < rows-1; j++ {
			for k := 0; k < rows-1; k++ {
				if k < i {
					tempDet[j][k] = matrix[j+1][k]
				} else {
					tempDet[j][k] = matrix[j+1][k+1]
				}
			}
		}
		dec := -1
		if (i)%2 == 0 {
			dec = 1
		} else {
			dec = -1
		}

		res += matrix[0][i] * dec * determinantSub2(tempDet, rows-1, rows-1)
	}
	return res
}
